#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {
        int work = group.size();
        vector<vector<vector<int>>> dp(work + 1, vector<vector<int>>(n + 1, vector<int>(minProfit + 1)));
        for (int j = 0; j <= n; j++) dp[0][j][0] = 1;
        for (int i = 1; i <= work; i++)
            for (int j = 0; j <= n; j++)
                for (int k = 0; k <= minProfit; k++)
                {
                    dp[i][j][k] = dp[i - 1][j][k];
                    if (j >= group[i - 1]) dp[i][j][k] += dp[i - 1][j - group[i - 1]][max(0, k - profit[i - 1])];
                    dp[i][j][k] %= 1000000007;
                }
        return dp[work][n][minProfit];
    }
};